package com.nlp.algorithm.dynamic;
/**
 * 给定一个矩阵m，从左上角开始每次只能向右走或者向下走，
 * 最后达到右下角的位置，路径中所有数字累加起来就是路径和，
 * 返回所有路径的最小路径和，如果给定的m如下，那么路径1,3,1,0,6,1,0就是最小路径和，返回12.
 * 1 3 5 9
 * 8 1 3 4
 * 5 0 6 1
 * 8 8 4 0
 * 
 * 分析：对于这个题目，假设m是m行n列的矩阵，
 * 那么我们用dp[m][n]来抽象这个问题，
 * dp[i][j]表示的是从原点到i,j位置的最短路径和。
 * 我们首先计算第一行和第一列，直接累加即可，
 * 那么对于其他位置，要么是从它左边的位置达到，
 * 要么是从上边的位置达到，我们取左边和上边的较小值，
 * 然后加上当前的路径值，就是达到当前点的最短路径。
 * 然后从左到右，从上到下依次计算即可。 
 * @author ygsong.abcft
 *
 *
 *给定一个矩阵m，从左上角开始每次只能想右走或者向下走
 *最后达到右下角的位置，路径中所有数字累加起来就是路径和
 *返回所有路径的最小路径和
 */
public class MinSteps {
	public static int[][] steps = new int[4][4];
	
	public static void main(String[] args) {
		int[][] arr = {{4,1,5,3},{3,2,7,7},{6,5,2,8},{8,9,4,5}};
		steps[3][3] = minSteps(arr, 3, 3);
		print(steps);
	}

	private static int minSteps(int[][] arr, int row, int col) {
		//如果起始位置，则直接返回
		if (row == 0 && col == 0) {
			steps[row][col] = arr[row][col];
			return steps[row][col];
		}
		//计算arr[row][col]的左面位置的值
		if (col >= 1 && steps[row][col-1] == 0) {
			steps[row][col-1] = minSteps(arr, row, col-1);
		}
		
		//计算arr[row][col]的上面位置的值
		if (row >= 1 && steps[row-1][col] == 0) {
			steps[row-1][col] = minSteps(arr, row-1, col);
		}
		
		//如果为第一行，则直接加左面位置上的值
		if (row == 0 && col != 0) {
			steps[row][col] = arr[row][col]+steps[row][col-1];
		}else if (col == 0 && row != 0) {
			//如果为第一列，则直接加上上面位置的值
			steps[row][col] = arr[row][col] + steps[row-1][col];
		}else {
			//比较到达左面位置和到达上面位置的值的大小，加上两者的最大值
			steps[row][col] = arr[row][col] + min(steps[row][col-1],steps[row-1][col]);
		}
		return steps[row][col];
	}
	
	private static int min(int minSteps, int minSteps2) {
		return minSteps > minSteps2? minSteps:minSteps2;
	}
	
	private static void print(int[][] arr) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++) {
				System.out.println("到达arr["+i+"]["+j+"]的最大路径："+arr[i][j]);
			}
		}
	}

	
}
